package seqlist.oj;

public class Num0204 {
    public ListNode partition(ListNode head, int x) {
        if(head==null || head.next==null){
            return head;
        }

        ListNode smallHead=new ListNode(-1);
        ListNode bigHead=new ListNode (-1);
        ListNode smallTail=smallHead;
        ListNode bigTail=bigHead;
        while(head != null){
            if(head.val < x){
                smallTail.next=head;
                smallTail=head;
                head=head.next;
            }else{
                bigTail.next=head;
                bigTail=head;
                head=head.next;
            }
        }
        bigTail.next=null;
        smallTail.next=bigHead.next;
        return smallHead.next;
    }
}
